#include "stdafx.h"
#include "cppflibinc.h"
#include <typeinfo>
#include <string.h>


using namespace cppflib;
using namespace cppflib::util;
using namespace cppflib::os;
using namespace cppflib::exceptions;
using namespace cppflib::collections;
using namespace cppflib::collections::tree;
using namespace cppflib::collections::sort;

static bool __SetArrayValue(int index, int &v)
{
   v = 123;

   return true;
}

static bool __SetArrayStringValue(int index, CFString *& s)
{
   if (s == NULL)
      s = new CFString(_S("123"));
   else
      *s = _S("123");

   return true;
}

static void TestArrayTemplate(void)
{
   cppmempool::MemPoolWrap localPool;

   // array of primitive type
   ArrayInt *a = new ArrayInt(10);

   for (int i = 0; i < (int)a->GetSize(); ++i)
      (*a)[i] = i + 2;

   for (int i = 0; i < (int)a->GetSize(); ++i)
      assert((*a)[i] == i + 2);

   ArrayInt b(20);
   assert(a->CopyTo(b, 0, 0, a->GetSize()));
   for (int i = 0; i < (int)b.GetSize(); ++i) {
      if (i < (int)a->GetSize())
         assert(b[i] == i + 2);
      else
         assert(b[i] == 0);
   }

   b.Resize(5); // shrink array
   for (int i = 0; i < (int)b.GetSize(); ++i) {
      assert(b[i] == i + 2);
   }

   b.Resize(10);  // expand it
   for (int i = 0; i < (int)b.GetSize(); ++i) {
      if (i < 5)
         assert(b[i] == i + 2);
      else
         assert(b[i] == 0);
   }

   // test out of bounds
   try {
      int tt = b[-1];
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   try {
      int tt = b[static_cast<int>(b.GetSize())];
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   // test foreach
   a->ForEach(ArrayInt::ForEachFuncS(&__SetArrayValue));
   for (int i = 0; i < (int)a->GetSize(); ++i)
      assert((*a)[i] == 123);


   // array of CFString pointers
   ArrayCppObjT<CFString> *pStr = new ArrayCppObjT<CFString>(10);

   for (int i = 0; i < (int)pStr->GetSize(); ++i) {
      pStr->Set(i, new CFString(""));
      pStr->Get(i)->Format(_S("***%d***"), i);
   }

   for (int i = 0; i < (int)pStr->GetSize(); ++i) {
      CFString temp("");
      temp.Format(_S("***%d***"), i);
      assert(pStr->Get(i)->Compare(temp) == 0);
   }

   
   ArrayCppObjT<CFString> bStr(20);
   assert(pStr->CopyTo(bStr, 0, 0, pStr->GetSize()));
   for (int i = 0; i < (int)pStr->GetSize(); ++i) {
      if (i < (int)pStr->GetSize()) {
         CFString temp("");
         temp.Format(_S("***%d***"), i);
         assert(bStr.Get(i)->Compare(temp) == 0);
      }
      else {
         assert(bStr.Get(i) == NULL);
      }
   }


   bStr.Resize(5); // shrink array
   for (int i = 0; i < (int)bStr.GetSize(); ++i) {
      CFString temp("");
      temp.Format(_S("***%d***"), i);
      assert(bStr.Get(i)->Compare(temp) == 0);
   }

   bStr.Resize(10); // expand it
   for (int i = 0; i < (int)bStr.GetSize(); ++i) {
      if (i < 5) {
         CFString temp("");
         temp.Format(_S("***%d***"), i);
         assert(bStr.Get(i)->Compare(temp) == 0);
      }
      else {
         assert(bStr.Get(i) == NULL);
      }
   }

   ArrayCppObjT<CFString> cStr(3);
   cStr.Set(0, new CFString("1"));
   cStr.Set(1, new CFString("2"));
   cStr.Set(2, new CFString("3"));
   
   cStr.CopyTo(bStr, 0, 0, 3);
   for (int i = 0; i < (int)bStr.GetSize(); ++i) {
      if (i < 3) {
         CFString temp("");
         temp.Format(_S("%d"), i + 1);
         assert(bStr.Get(i)->Compare(temp) == 0);
      }
      else if (i < 5) {
         CFString temp("");
         temp.Format(_S("***%d***"), i);
         assert(bStr.Get(i)->Compare(temp) == 0);
      }
      else {
         assert(bStr.Get(i) == NULL);
      }
   }

   // test out of bounds
   try {
      cStr.Get(-1);
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &e) {
      debug::Print(debug::DL_DEBUG, _S("cStr -- %s\n"), e.GetMsg());
   }

   try {
      cStr.Get(static_cast<int>(cStr.GetSize()));
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &e) {
      debug::Print(debug::DL_DEBUG, _S("cStr -- %s\n"), e.GetMsg());
   }


   cStr.ForEach(ArrayCppObjT<CFString>::ForEachFuncS(&__SetArrayStringValue));
   for (int i = 0; i < (int)cStr.GetSize(); ++i)
      assert(*cStr.Get(i) == _S("123"));

}

static void TestCopyArray()
{  
   debug::Print(_S("Testing copy array ...\n"));

   cppmempool::MemPoolWrap localPool;

   const int BUFSIZE = 15; 

   int buf[BUFSIZE];
   ArrayInt * pIntArray = new ArrayInt(BUFSIZE);
   for (int i = 0; i < BUFSIZE; ++i)
      buf[i] = i + 1;

   pIntArray->CopyFrom(buf, BUFSIZE, 0, 0, BUFSIZE);
   for (int i = 0; i < static_cast<int>(pIntArray->GetSize()); ++i)
      assert((*pIntArray)[i] == (i + 1));

   ArrayInt * pIntArray2 = new ArrayInt(BUFSIZE);
   pIntArray->CopyTo(*pIntArray2, BUFSIZE);

   for (int i = 0; i < static_cast<int>(pIntArray2->GetSize()); ++i)
      assert((*pIntArray2)[i] == (i + 1));


   ArrayCppObjT<CFString> * pStrArray = new ArrayCppObjT<CFString>(BUFSIZE);
   for (int i = 0; i < BUFSIZE; ++i)
      pStrArray->Set(i, new CFString(CFString::SFormat(_S("Hello %d"), i)));

   ArrayCppObjT<CFString> * pStrArray2 = new ArrayCppObjT<CFString>(BUFSIZE);
   ArrayCppObjT<CFString> * pStrArray3 = new ArrayCppObjT<CFString>(BUFSIZE);

   pStrArray->CopyTo(*pStrArray2, BUFSIZE);
   for (int i = 0; i < static_cast<int>(pStrArray2->GetSize()); ++i)
      assert(*pStrArray2->Get(i) == CFString::SFormat(_S("Hello %d"), i) );

   pStrArray3->CopyFrom(*pStrArray2, BUFSIZE);
   for (int i = 0; i < static_cast<int>(pStrArray3->GetSize()); ++i)
      assert(*pStrArray3->Get(i) == CFString::SFormat(_S("Hello %d"), i) );

}

static void TestListTemplate()
{
   debug::Print(_S("Testing list template ...\n"));

   cppmempool::MemPoolWrap localPool;

   const int LISTNUM = 3;
   ListInt a;

   for (int i = 0; i < LISTNUM; ++i)
      a.AddTail(i + 1);

   for (int i = 0; i < (int)a.GetCount(); ++i)
      assert(a.Get(i) == i + 1);

   a.AddHead(100);
   a.AddHead(200);

   assert(a.Get(0) == 200);
   assert(a.Get(1) == 100);
   for (int i = 2; i < (int)a.GetCount(); ++i)
      assert(a.Get(i) == i - 2 + 1);

   a.Insert(0, 300);
   a.Insert(3, 400);
   a.Insert((int)a.GetCount(), 500);


   assert(a.Get(4) == 1);
   assert(a.Get(5) == 2);
   assert(a.Get(6) == 3);
   assert(a.Get(7) == 500);
   assert(a.Get(0) == 300);
   assert(a.Get(1) == 200);
   assert(a.Get(2) == 100);
   assert(a.Get(3) == 400);
   
   a.RemoveAt(1);
   a.RemoveAt(3);
   a.RemoveAt(5);

   assert(a.Get(0) == 300);
   assert(a.Get(1) == 100);
   assert(a.Get(2) == 400);
   assert(a.Get(3) == 2);
   assert(a.Get(4) == 3);
   assert(a.GetHead() == 300);
   assert(a.GetTail() == 3);

   a.Clear();
   assert(a.GetCount() == 0);

   ////////////////////////////////////////

   for (int i = 0; i < LISTNUM; ++i)
      a.AddTail(i + 1);

   assert(a.Get(1) == 2);
   a.Insert(1, 100);
   assert(a.Get(1) == 100);
   assert(a.Get(2) == 2);
   a.RemoveAt(2);
   assert(a.Get(2) == 3);
   a.AddHead(500);
   assert(a.Get(2) == 100);
   a.AddTail(700);
   assert(a.Get(2) == 100);
   assert(a.Set(2, 3854) == 100);
   assert(a.Get(2) == 3854);

   // test out of bound
   try {
      a.Get(static_cast<int>(-1));
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   try {
      a.Get(static_cast<int>(a.GetCount()));
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   try {
      a.RemoveAt(-1);
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   try {
      a.RemoveAt(static_cast<int>(a.GetCount()));
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   a.ForEach(ListInt::ForEachFuncS(&__SetArrayValue));
   for (int i = 0; i < (int)a.GetCount(); ++i)
      assert(a.Get(i) == 123);
}

static void TestListPtrTemplate(void)
{
   debug::Print(_S("Testing list ptr template ...\n"));

   cppmempool::MemPoolWrap localPool;

   const int LISTNUM = 3;
   ListCppObjT<CFString> a;

   a.AddTail(new CFString("abc"));
   a.AddTail(new CFString("123"));
   a.AddTail(new CFString("axd"));

   assert(a.Get(0)->Compare(_S("abc")) == 0);
   assert(a.Get(1)->Compare(_S("123")) == 0);
   assert(a.Get(2)->Compare(_S("axd")) == 0);
   assert(a.GetHead()->Compare(_S("abc")) == 0);
   assert(a.GetTail()->Compare(_S("axd")) == 0);

   a.AddHead(new CFString("098765"));
   a.Insert(0, new CFString("plmko"));
   
   assert(a.Get(0)->Compare(_S("plmko")) == 0);
   assert(a.Get(1)->Compare(_S("098765")) == 0);

   a.RemoveAt(2);
   a.RemoveAt(3);

   assert(a.GetCount() == 3);
   assert(a.Get(2)->Compare(_S("123")) == 0);
   a.Set(1, a.Get(1));
   assert(*a.Get(1) == _S("098765"));
   a.Set(0, a.Get(1));
   assert(*a.Get(0) == _S("098765"));
   a.Set(0, new CFString("fffrer"));
   assert(*a.Get(0) == _S("fffrer"));
   assert(*a.Get(1) == _S("098765"));

   a.Clear();

   assert(a.GetCount() == 0);

   // test out of bound
   try {
      a.Get(static_cast<int>(-1));
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   try {
      a.Get(static_cast<int>(a.GetCount()));
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   try {
      a.RemoveAt(-1);
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   try {
      a.RemoveAt(static_cast<int>(a.GetCount()));
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }


   a.AddTail(new CFString("abc"));
   a.AddTail(new CFString("123"));
   a.AddTail(new CFString("axd"));
   a.ForEach(ListCppObjT<CFString>::ForEachFuncS(&__SetArrayStringValue));
   for (int i = 0; i < (int)a.GetCount(); ++i)
      assert(*a.Get(i) == _S("123"));
}

static void EnumHashTable(HashtableT<CFString, CFString> *table, int num)
{
   u64_t pos = 0;
   int count = 0;
   const CFString *pKey = NULL;
   CFString *pVal = NULL;
   while (table->EnumerateElement(pos, &pKey, &pVal)) {
      assert(pKey != NULL);
      ++count;
   }
   assert(count == num);
}

static void EnumHashTable_2(HashtableT<CFString, CFString> *table, int num)
{
   u64_t pos = 0;
   int count = 0;
   // enumerate without passing key and value pointer
   while (table->EnumerateElement(pos, NULL, NULL)) {
      ++count;
   }
   assert(count == num);
}

static void TestHashtable(void)
{
   debug::Print(_S("Testing Hashtable ...\n"));

   cppmempool::MemPoolWrap localPool;
   
   CFString *pKey = NULL, *pVal = NULL;
   HashtableT<CFString, CFString> *table = new HashtableT<CFString, CFString>();

   assert(table->GetCount() == 0);
   EnumHashTable(table, 0);

   table->Set(new CFString("1111"), new CFString("abcd"));
   table->Set(new CFString("2222"), new CFString("qwert"));
   table->Set(new CFString("3333"), new CFString("mary"));
   table->Set(new CFString("9281"), new CFString("peter"));
   table->Set(new CFString("MIMI"), new CFString("john"));
   table->Set(new CFString("__qwe"), new CFString("harry"));
   table->Set(new CFString("flag"), new CFString("macy"));

   assert(table->GetCount() == 7);

   pKey = new CFString("flag");

   assert(table->Get(*pKey)->Compare(_S("macy")) == 0);
   // set with same value
   table->Set(pKey, new CFString("1234"));

   assert(table->GetCount() == 7);
   assert(table->Get(*pKey)->Compare(_S("1234")) == 0);

   // set with a new value
   table->Set(new CFString("flag2"), new CFString("67890"));
   assert(table->GetCount() == 8);

   pKey = new CFString("qqqqq");
   // add a NULL value
   table->Set(pKey, NULL);
   assert(table->GetCount() == 9);

   // add a NULL key
   table->Set(NULL, NULL);
   assert(table->GetCount() == 9);

   assert(table->ContainsKey(*pKey));
   assert(table->Get(*pKey) == NULL);

   pKey = new CFString("__qwe");
   assert(table->ContainsKey(*pKey));
   assert(table->ContainsValue(CFString("peter")));
   //assert(!table->ContainsValue(NULL));
   assert(!table->ContainsKey(CFString("4444")));

   pVal = table->Get(*pKey);
   assert(pVal->Compare(_S("harry")) == 0);

   table->Remove(*pKey);
   assert(table->GetCount() == 8);
   table->Remove(CFString("3333"));
   assert(table->GetCount() == 7);

   // enumerate all elements
   EnumHashTable(table, 7);
   table->Set(new CFString("GOO"), new CFString("uuuuuu"));
   EnumHashTable(table, 8);
   table->Remove(CFString("MIMI"));
   EnumHashTable_2(table, 7);

   // clear all
   table->Clear();
   assert(table->GetCount() == 0);

}


/**
 *  A class derived from TreeNode
 */
class MyTreeNode : public TreeNode
{
private:
    int value;
    MyTreeNode(void)
    {
       value = 0;
    }
public:
    MyTreeNode(int value) 
    {
       this->value = value;
    }

    virtual ~MyTreeNode(void)
    {

    }

    int GetValue()
    {
       return value;
    }

    virtual int Compare(const TreeNode &treeNode)
    {
       if (this->EqualType(treeNode)) {
          return this->value - static_cast<const MyTreeNode*>(&treeNode)->value;
       }
       
       return (int)-1;
    }

    virtual void CopyFromNode(const TreeNode &treeNode)
    {
        this->value = static_cast<const MyTreeNode*>(&treeNode)->value;
    }

    virtual bool Equals(BaseObject &obj) const
    {
       if (this->EqualType(obj)) {
          return static_cast<MyTreeNode*>(&obj)->value == this->value;
       }

       return false;   
    }

    virtual u32_t GetHash(void) const
    {
       return (u32_t)this->value;
    }

    virtual pcwstr_t ToString(void) const
    {
       CFString * pStr = new CFString();
       pStr->Format(_S("%d"), this->value);
       return pStr->ToString();
    }
};

typedef enum {
   TEST_NONE = 0,
   TEST_BREATHFIRST,
   TEST_INORDER,
   TEST_PREORDER,
   TEST_POSTORDER,

   TEST_BREATHFIRST_A,
   TEST_BREATHFIRST_B,
   TEST_BREATHFIRST_C,
   TEST_BREATHFIRST_D,
} treewalktype_t;

static treewalktype_t st_treewalk = TEST_NONE;
static int st_nodeIndex = 0;

static void TreeWalk(TreeNode * pNode)
{
    int v = static_cast<MyTreeNode*>(pNode)->GetValue();
    switch(st_treewalk) {
       case TEST_BREATHFIRST:
          switch (st_nodeIndex) {
             case 0: assert(v == 6); break;
             case 1: assert(v == 4); break;
             case 2: assert(v == 23); break;
             case 3: assert(v == 2); break;
             case 4: assert(v == 10); break;
             case 5: assert(v == 26); break;
             case 6: assert(v == 11); break;
          }
          break;
       case TEST_INORDER:
          switch (st_nodeIndex) {
             case 0: assert(v == 2); break;
             case 1: assert(v == 4); break;
             case 2: assert(v == 6); break;
             case 3: assert(v == 10); break;
             case 4: assert(v == 11); break;
             case 5: assert(v == 23); break;
             case 6: assert(v == 26); break;
          }
          break;
       case TEST_PREORDER:
          switch (st_nodeIndex) {
             case 0: assert(v == 6); break;
             case 1: assert(v == 4); break;
             case 2: assert(v == 2); break;
             case 3: assert(v == 23); break;
             case 4: assert(v == 10); break;
             case 5: assert(v == 11); break;
             case 6: assert(v == 26); break;
          }
          break;
       case TEST_POSTORDER:
          switch (st_nodeIndex) {
             case 0: assert(v == 2); break;
             case 1: assert(v == 4); break;
             case 2: assert(v == 11); break;
             case 3: assert(v == 10); break;
             case 4: assert(v == 26); break;
             case 5: assert(v == 23); break;
             case 6: assert(v == 6); break;
          }
          break;
    }

    ++st_nodeIndex;
}

static void TreeWalk_2(TreeNode * pNode)
{
   int v = static_cast<MyTreeNode*>(pNode)->GetValue();
    switch(st_treewalk) {
       case TEST_BREATHFIRST_A:
          switch (st_nodeIndex) {
             case 0: assert(v == 6); break;
             case 1: assert(v == 4); break;
             case 2: assert(v == 23); break;
             case 3: assert(v == 2); break;
             case 4: assert(v == 11); break;
             case 5: assert(v == 26); break;
          } 
          break;
       case TEST_BREATHFIRST_B:
          switch (st_nodeIndex) {
             case 0: assert(v == 6); break;
             case 1: assert(v == 2); break;
             case 2: assert(v == 23); break;
             case 3: assert(v == 11); break;
             case 4: assert(v == 26); break;
          } 
          break;
       case TEST_BREATHFIRST_C:
          switch (st_nodeIndex) {
             case 0: assert(v == 6); break;
             case 1: assert(v == 2); break;
             case 2: assert(v == 26); break;
             case 3: assert(v == 11); break;
          } 
          break;
       case TEST_BREATHFIRST_D:
          switch (st_nodeIndex) {
             case 0: assert(v == 6); break;
             case 1: assert(v == 2); break;
             case 2: assert(v == 26); break;
          } 
          break;
    }

    ++st_nodeIndex;
}

static void TestBinTree(void)
{
    debug::Print(_S("Testing bin tree ...\n"));

    cppmempool::MemPoolWrap localPool;

    BinTree *pTree = new BinTree();
    assert(pTree->IsTreeEmpty());
    pTree->Insert(new MyTreeNode(6));
    pTree->Insert(new MyTreeNode(23));
    pTree->Insert(new MyTreeNode(10));
    pTree->Insert(new MyTreeNode(4));
    pTree->Insert(new MyTreeNode(2));
    pTree->Insert(new MyTreeNode(26));
    pTree->Insert(new MyTreeNode(11));
    assert(pTree->GetCount() == 7);
    assert(!pTree->IsTreeEmpty());

    /////// tree walk
    debug::Print(_S("Testing bin tree tree walk...\n"));
    pTree->SetTreeWalkCallback(TreeWalkCallback(&TreeWalk));
    
    st_treewalk = TEST_BREATHFIRST;
    st_nodeIndex = 0;
    pTree->BreathFirstTraverse();

    st_treewalk = TEST_INORDER;
    st_nodeIndex = 0;
    pTree->InorderWalk();

    st_treewalk = TEST_PREORDER;
    st_nodeIndex = 0;
    pTree->PreorderWalk();

    st_treewalk = TEST_POSTORDER;
    st_nodeIndex = 0;
    pTree->PostorderWalk();

    // normal operations
    debug::Print(_S("Testing bin tree normal operations ...\n"));
    TreeNode *pNode = pTree->GetMin();
    assert(static_cast<MyTreeNode*>(pNode)->GetValue() == 2);

    pNode = pTree->GetSuccessor(pNode);
    assert(static_cast<MyTreeNode*>(pNode)->GetValue() == 4);

    pNode = pTree->GetMax();
    assert(static_cast<MyTreeNode*>(pNode)->GetValue() == 26);

    pNode = pTree->GetPredecessor(pNode);
    assert(static_cast<MyTreeNode*>(pNode)->GetValue() == 23);


    MyTreeNode temp(10);
    assert(pTree->Search(temp) != NULL);

    MyTreeNode temp2(6);
    assert(pTree->Search(temp2) != NULL);

    MyTreeNode temp3(12);
    assert(pTree->Search(temp3) == NULL);

    ////// delete nodes
    debug::Print(_S("Testing bin tree delete nodes ...\n"));
    pTree->SetTreeWalkCallback(TreeWalkCallback(&TreeWalk_2));
    MyTreeNode del1(10);   // one right child
    assert(pTree->Delete(del1));
    assert(pTree->GetCount() == 6);

    st_treewalk = TEST_BREATHFIRST_A;
    st_nodeIndex = 0;
    pTree->BreathFirstTraverse();

    MyTreeNode del2(4);   // one left child
    assert(pTree->Delete(del2));
    assert(pTree->GetCount() == 5);

    st_treewalk = TEST_BREATHFIRST_B;
    st_nodeIndex = 0;
    pTree->BreathFirstTraverse();

    MyTreeNode del3(23);   // 2 children
    assert(pTree->Delete(del3));
    assert(pTree->GetCount() == 4);

    st_treewalk = TEST_BREATHFIRST_C;
    st_nodeIndex = 0;
    pTree->BreathFirstTraverse();

    MyTreeNode del4(11);   // no child
    assert(pTree->Delete(del4));
    assert(pTree->GetCount() == 3);

    st_treewalk = TEST_BREATHFIRST_D;
    st_nodeIndex = 0;
    pTree->BreathFirstTraverse();

    pTree->FreeTree();
    assert(pTree->GetCount() == 0);


    ///////// test casting with runtime type checking //////////
    assert(cppflib::InstanceOf<MyTreeNode>(pNode)); // casting should be OK
    assert(!cppflib::InstanceOf<MyTreeNode>(pTree));       // casting should fail
    
}

/**
 *  A class derived from AvlTreeNode
 */
class MyAvlTreeNode : public AvlTreeNode
{
private:
    CFString *value;
    MyAvlTreeNode(void)
    {
       value = new CFString("");
       cppmempool::Retain(value);
    }
public:
    MyAvlTreeNode(pcwstr_t str)
    {
       value = new CFString(str);
       cppmempool::Retain(value);
    }

    ~MyAvlTreeNode()
    {
       cppmempool::Release(value);
    }

    pcwstr_t GetValue() const
    {
       return value->operator pcwstr_t();
    }

    virtual int Compare(const TreeNode &treeNode)
    {
       if (!cppflib::InstanceOf<const MyAvlTreeNode>(&treeNode))
          return -1;

       const MyAvlTreeNode& otherNode = static_cast<const MyAvlTreeNode&>(treeNode);
       return this->value->Compare(otherNode.GetValue());
    }

    virtual void CopyFromNode(const TreeNode &treeNode)
    {
        if (!cppflib::InstanceOf<const MyAvlTreeNode>(&treeNode))
           throw ArgumentException(_S("treeNode isn't an instance of MyAvlTreeNode"));

        *this->value = *static_cast<const MyAvlTreeNode&>(treeNode).value;
    }

    virtual bool Equals(BaseObject &obj) const
    {
       if (!cppflib::InstanceOf<const MyAvlTreeNode>(&obj))
          return false;
       
       const MyAvlTreeNode& otherNode = static_cast<const MyAvlTreeNode&>(obj);
       return *this->value == otherNode.GetValue();
       
       return false;
    }

    virtual u32_t GetHash(void) const
    {
       return (u32_t)this->value->GetHash();
    }

    virtual pcwstr_t ToString(void) const
    {
       return this->value->operator pcwstr_t();
    }

};

static void __AvlTreeWalk(TreeNode * pNode)
{
    MyAvlTreeNode * pMyNode = static_cast<MyAvlTreeNode*>(pNode);
    int bFactor = pMyNode->GetBalanceFactor();
    assert(bFactor >= -1 && bFactor <= 1);
    //printf("value = %s\n", CFString(pMyNode->GetValue()).ToUtf8String());
}

static int totalDepthCount = 4;

static void __AvlTreeWalkPostOrder(TreeNode * pNode)
{
    MyAvlTreeNode * pMyNode = static_cast<MyAvlTreeNode*>(pNode);
    int bFactor = pMyNode->GetBalanceFactor();
    assert(bFactor >= -1 && bFactor <= 1);
    int depth = pMyNode->GetDepth();
    //printf("depth = %d\n", depth);
    assert(depth >= 0 && depth <= totalDepthCount);
}

static void TestAvlTree(void)
{
    debug::Print(_S("Testing avl tree ...\n"));

    cppmempool::MemPoolWrap localPool;

    AvlTree *pAvlTree = new AvlTree();
    assert(pAvlTree->IsTreeEmpty());
debug::Print(_S("Testing avl tree 1 ...\n"));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("Among"))));
debug::Print(_S("Testing avl tree 2 ...\n"));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("the"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("primitive"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("species"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("identified"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("there"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("is"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("considerable"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("variation"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("in"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("size"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("but"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("there"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("are"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("few"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("other"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("specific"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("adaptations"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("Modern"))));
    assert(pAvlTree->Insert(new MyAvlTreeNode(_S("birds"))));
    assert(pAvlTree->GetCount() == 20);

    pAvlTree->SetTreeWalkCallback(TreeWalkCallback(&__AvlTreeWalk));
    pAvlTree->BreathFirstTraverse();

    assert(CFString::WStrcmp(_S("variation"), static_cast<MyAvlTreeNode*>(pAvlTree->GetMax())->GetValue()) == 0);
    assert(CFString::WStrcmp(_S("Among"), static_cast<MyAvlTreeNode*>(pAvlTree->GetMin())->GetValue()) == 0);
    assert(CFString::WStrcmp(_S("primitive"), static_cast<MyAvlTreeNode*>(pAvlTree->GetRootNode())->GetValue()) == 0);

    totalDepthCount = 4;
    pAvlTree->SetTreeWalkCallback(TreeWalkCallback(&__AvlTreeWalkPostOrder));
    pAvlTree->PostorderWalk();

    // Deleting nodes
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("birds"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("Modern"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("adaptations"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("specific"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("other"))));
    assert(pAvlTree->GetCount() == 15);
    
    totalDepthCount = 4;
    pAvlTree->SetTreeWalkCallback(TreeWalkCallback(&__AvlTreeWalkPostOrder));
    pAvlTree->PostorderWalk();

    assert(pAvlTree->Delete(MyAvlTreeNode(_S("few"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("are"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("there"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("but"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("size"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("in"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("variation"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("considerable"))));
    assert(pAvlTree->GetCount() == 7);

    totalDepthCount = 3;
    pAvlTree->SetTreeWalkCallback(TreeWalkCallback(&__AvlTreeWalkPostOrder));
    pAvlTree->PostorderWalk();

    assert(pAvlTree->Delete(MyAvlTreeNode(_S("is"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("there"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("identified"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("species"))));
    assert(pAvlTree->GetCount() == 3);

    totalDepthCount = 1;
    pAvlTree->SetTreeWalkCallback(TreeWalkCallback(&__AvlTreeWalkPostOrder));
    pAvlTree->PostorderWalk();

    assert(pAvlTree->Delete(MyAvlTreeNode(_S("primitive"))));
    assert(pAvlTree->Delete(MyAvlTreeNode(_S("the"))));
    assert(pAvlTree->GetCount() == 1);
    
    totalDepthCount = 0;
    pAvlTree->SetTreeWalkCallback(TreeWalkCallback(&__AvlTreeWalkPostOrder));
    pAvlTree->PostorderWalk();

    assert(pAvlTree->Delete(MyAvlTreeNode(_S("Among"))));
    assert(pAvlTree->GetCount() == 0);
    assert(pAvlTree->IsTreeEmpty());
}

/**
 *  A class derived from AvlTreeNode
 */
class MyAvlIntNode : public AvlTreeNode
{
private:
    int value;
    MyAvlIntNode(void)
    {
       value = 0;
    }
public:
    MyAvlIntNode(int v)
    {
       value = v;
    }

    ~MyAvlIntNode()
    {
    }

    int GetValue() const
    {
       return value;
    }

    virtual int Compare(const TreeNode &treeNode)
    {
       if (!cppflib::InstanceOf<const MyAvlIntNode>(&treeNode))
          return -1;
       
       const MyAvlIntNode& otherNode = static_cast<const MyAvlIntNode&>(treeNode);
       return this->value - otherNode.value;       
    }

    virtual void CopyFromNode(const TreeNode &treeNode)
    {
        if (!cppflib::InstanceOf<const MyAvlIntNode>(&treeNode))
           throw ArgumentException(_S("treeNode isn't an instance of MyAvlIntNode"));

        this->value = static_cast<const MyAvlIntNode&>(treeNode).value;
    }

    virtual bool Equals(BaseObject &obj)
    {
       if (!cppflib::InstanceOf<const MyAvlIntNode>(&obj))
          return false;
       
       const MyAvlIntNode& otherNode = static_cast<const MyAvlIntNode&>(obj);
       return this->value == otherNode.value;
    }

    virtual u32_t GetHash(void)
    {
       return (u32_t)this->value;
    }

};

static int st_intNodeIndex = 0;
static int st_treeWalkRound = 0;

static void __AvlIntTreeWalk(TreeNode * pNode)
{
    MyAvlIntNode * pMyNode = static_cast<MyAvlIntNode*>(pNode);
    int bFactor = pMyNode->GetBalanceFactor();
    assert(bFactor >= -1 && bFactor <= 1);
    int depth = pMyNode->GetDepth();
    assert(depth >= 0 && depth <= 4);
    
    if (st_treeWalkRound == 0) {
        //printf("value = %d, balance = %d\n", pMyNode->GetValue(), pMyNode->GetBalanceFactor());

        switch(st_intNodeIndex) {
           

           case 0: assert(pMyNode->GetValue() == 33); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 1: assert(pMyNode->GetValue() == 3); 
                   assert(pMyNode->GetBalanceFactor() == 1); break;
           case 2: assert(pMyNode->GetValue() == 55); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 3: assert(pMyNode->GetValue() == 2); 
                   assert(pMyNode->GetBalanceFactor() == -1); break;
           case 4: assert(pMyNode->GetValue() == 10); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 5: assert(pMyNode->GetValue() == 35); 
                   assert(pMyNode->GetBalanceFactor() == 1); break;
           case 6: assert(pMyNode->GetValue() == 57); 
                   assert(pMyNode->GetBalanceFactor() == 1); break;
           case 7: assert(pMyNode->GetValue() == 1); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 8: assert(pMyNode->GetValue() == 5); 
                   assert(pMyNode->GetBalanceFactor() == -1); break;
           case 9: assert(pMyNode->GetValue() == 11); 
                   assert(pMyNode->GetBalanceFactor() == 1); break;
           case 10: assert(pMyNode->GetValue() == 34); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 11: assert(pMyNode->GetValue() == 45); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;  
           case 12: assert(pMyNode->GetValue() == 56); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 13: assert(pMyNode->GetValue() == 90); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 14: assert(pMyNode->GetValue() == 4); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 15: assert(pMyNode->GetValue() == 23); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 16: assert(pMyNode->GetValue() == 44); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 17: assert(pMyNode->GetValue() == 46); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 18: assert(pMyNode->GetValue() == 78); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 19: assert(pMyNode->GetValue() == 99); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;

        }

    }
    else if (st_treeWalkRound == 1) {
        //printf("value = %d, balance = %d\n", pMyNode->GetValue(), pMyNode->GetBalanceFactor());

        switch(st_intNodeIndex) {
           case 0: assert(pMyNode->GetValue() == 23); 
                   assert(pMyNode->GetBalanceFactor() == 1); break;
           case 1: assert(pMyNode->GetValue() == 5); 
                   assert(pMyNode->GetBalanceFactor() == -1); break;
           case 2: assert(pMyNode->GetValue() == 46); 
                   assert(pMyNode->GetBalanceFactor() == 1); break;
           case 3: assert(pMyNode->GetValue() == 3); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 4: assert(pMyNode->GetValue() == 11); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 5: assert(pMyNode->GetValue() == 44); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 6: assert(pMyNode->GetValue() == 57); 
                   assert(pMyNode->GetBalanceFactor() == 1); break;
           case 7: assert(pMyNode->GetValue() == 1); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 8: assert(pMyNode->GetValue() == 4); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 9: assert(pMyNode->GetValue() == 35); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 10: assert(pMyNode->GetValue() == 45); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 11: assert(pMyNode->GetValue() == 56); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 12: assert(pMyNode->GetValue() == 90); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 13: assert(pMyNode->GetValue() == 78); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
           case 14: assert(pMyNode->GetValue() == 99); 
                    assert(pMyNode->GetBalanceFactor() == 0); break;
        }

    }
    else if (st_treeWalkRound == 2) {
        //printf("value = %d, balance = %d\n", pMyNode->GetValue(), pMyNode->GetBalanceFactor());

        switch(st_intNodeIndex) {
           case 0: assert(pMyNode->GetValue() == 46); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 1: assert(pMyNode->GetValue() == 23); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 2: assert(pMyNode->GetValue() == 90); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 3: assert(pMyNode->GetValue() == 4); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 4: assert(pMyNode->GetValue() == 44); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 5: assert(pMyNode->GetValue() == 57); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 6: assert(pMyNode->GetValue() == 99); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
       }
    }
    else if (st_treeWalkRound == 3) {
        //printf("value = %d, balance = %d\n", pMyNode->GetValue(), pMyNode->GetBalanceFactor());

        switch(st_intNodeIndex) {
           case 0: assert(pMyNode->GetValue() == 90); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 1: assert(pMyNode->GetValue() == 44); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
           case 2: assert(pMyNode->GetValue() == 99); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
       }
    }
    else if (st_treeWalkRound == 4) {
        //printf("value = %d, balance = %d\n", pMyNode->GetValue(), pMyNode->GetBalanceFactor());

        switch(st_intNodeIndex) {
           case 0: assert(pMyNode->GetValue() == 44); 
                   assert(pMyNode->GetBalanceFactor() == 0); break;
       }
    }


    ++st_intNodeIndex;
}

static void TestAvlTree_2()
{
    debug::Print(_S("Testing avl tree 2 ...\n"));

    cppmempool::MemPoolWrap localPool;

    AvlTree *pAvlTree = new AvlTree();
    assert(pAvlTree->IsTreeEmpty());

    assert(pAvlTree->Insert(new MyAvlIntNode(10)));
    assert(pAvlTree->Insert(new MyAvlIntNode(2)));
    assert(pAvlTree->Insert(new MyAvlIntNode(34)));
    assert(pAvlTree->Insert(new MyAvlIntNode(33)));
    assert(pAvlTree->Insert(new MyAvlIntNode(55)));
    assert(pAvlTree->Insert(new MyAvlIntNode(11)));
    assert(pAvlTree->Insert(new MyAvlIntNode(56)));
    assert(pAvlTree->Insert(new MyAvlIntNode(45)));
    assert(pAvlTree->Insert(new MyAvlIntNode(3)));
    assert(pAvlTree->Insert(new MyAvlIntNode(1)));
    assert(pAvlTree->Insert(new MyAvlIntNode(5)));
    assert(pAvlTree->Insert(new MyAvlIntNode(35)));
    assert(pAvlTree->Insert(new MyAvlIntNode(78)));
    assert(pAvlTree->Insert(new MyAvlIntNode(23)));
    assert(pAvlTree->Insert(new MyAvlIntNode(46)));
    assert(pAvlTree->Insert(new MyAvlIntNode(57)));
    assert(pAvlTree->Insert(new MyAvlIntNode(4)));
    assert(pAvlTree->Insert(new MyAvlIntNode(90)));
    assert(pAvlTree->Insert(new MyAvlIntNode(99)));
    assert(pAvlTree->Insert(new MyAvlIntNode(44)));
    assert(pAvlTree->GetCount() == 20);

    pAvlTree->SetTreeWalkCallback(TreeWalkCallback(&__AvlIntTreeWalk));
    pAvlTree->BreathFirstTraverse();

    assert(static_cast<MyAvlIntNode*>(pAvlTree->GetMax())->GetValue() == 99);
    assert(static_cast<MyAvlIntNode*>(pAvlTree->GetMin())->GetValue() == 1);
    assert(static_cast<MyAvlIntNode*>(pAvlTree->GetRootNode())->GetValue() == 33);

    //printf("===================================\n");
    // Delete 5 nodes
    assert(pAvlTree->Delete(MyAvlIntNode(10)));
    assert(pAvlTree->Delete(MyAvlIntNode(2)));
    assert(pAvlTree->Delete(MyAvlIntNode(34)));
    assert(pAvlTree->Delete(MyAvlIntNode(33)));
    assert(pAvlTree->Delete(MyAvlIntNode(55)));
    assert(pAvlTree->GetCount() == 15);

    st_intNodeIndex = 0;
    st_treeWalkRound = 1;
    pAvlTree->SetTreeWalkCallback(TreeWalkCallback(&__AvlIntTreeWalk));
    pAvlTree->BreathFirstTraverse();

    // Delete 8 nodes
    assert(pAvlTree->Delete(MyAvlIntNode(11)));
    assert(pAvlTree->Delete(MyAvlIntNode(56)));
    assert(pAvlTree->Delete(MyAvlIntNode(45)));
    assert(pAvlTree->Delete(MyAvlIntNode(3)));
    assert(pAvlTree->Delete(MyAvlIntNode(1)));
    assert(pAvlTree->Delete(MyAvlIntNode(5)));
    assert(pAvlTree->Delete(MyAvlIntNode(35)));
    assert(pAvlTree->Delete(MyAvlIntNode(78)));
    assert(pAvlTree->GetCount() == 7);

    st_intNodeIndex = 0;
    st_treeWalkRound = 2;
    pAvlTree->SetTreeWalkCallback(TreeWalkCallback(&__AvlIntTreeWalk));
    pAvlTree->BreathFirstTraverse();

    // Delete 4 nodes
    assert(pAvlTree->Delete(MyAvlIntNode(23)));
    assert(pAvlTree->Delete(MyAvlIntNode(46)));
    assert(pAvlTree->Delete(MyAvlIntNode(57)));
    assert(pAvlTree->Delete(MyAvlIntNode(4)));
    assert(pAvlTree->GetCount() == 3);

    st_intNodeIndex = 0;
    st_treeWalkRound = 3;
    pAvlTree->SetTreeWalkCallback(TreeWalkCallback(&__AvlIntTreeWalk));
    pAvlTree->BreathFirstTraverse();

    // Delete 2 nodes
    assert(pAvlTree->Delete(MyAvlIntNode(90)));
    assert(pAvlTree->Delete(MyAvlIntNode(99)));
    assert(pAvlTree->GetCount() == 1);

    st_intNodeIndex = 0;
    st_treeWalkRound = 4;
    pAvlTree->SetTreeWalkCallback(TreeWalkCallback(&__AvlIntTreeWalk));
    pAvlTree->BreathFirstTraverse();

    // Delete last node
    assert(pAvlTree->Delete(MyAvlIntNode(44)));
    assert(pAvlTree->GetCount() == 0);
    assert(pAvlTree->IsTreeEmpty());
}

static void TestQueue()
{
    cppmempool::MemPoolWrap localPool;

    // normal queue
    QueueInt * intQueue = new QueueInt(false);
    assert(intQueue->GetCount() == 0);
    intQueue->Enqueue(2);
    intQueue->Enqueue(3);
    intQueue->Enqueue(1);
    assert(intQueue->Contains(3));
    assert( ! intQueue->Contains(55));
    assert(intQueue->Peek() == 2);
    assert(intQueue->Dequeue() == 2);
    assert(intQueue->GetCount() == 2);
    assert(intQueue->Peek() == 3);
    assert(intQueue->Dequeue() == 3);
    assert(intQueue->GetCount() == 1);
    assert(intQueue->Dequeue() == 1);
    assert(intQueue->GetCount() == 0);

    intQueue->Enqueue(4);
    intQueue->Enqueue(11);
    intQueue->Enqueue(100);
    assert(intQueue->GetCount() == 3);
    intQueue->Clear();
    assert(intQueue->GetCount() == 0);

    // test out of bound
    try {
       intQueue->Dequeue();
       assert(false);  // should not get this line run
    }
    catch(OutOfBoundsException &) {
    }

    try {
       intQueue->Peek();
       assert(false);  // should not get this line run
    }
    catch(OutOfBoundsException &) {
    }

    // BaseObject Queue
    QueueCppObjT<CFString> * strQueue = new QueueCppObjT<CFString>(true);
    strQueue->Enqueue(new CFString(_S("good")));
    strQueue->Enqueue(new CFString(_S("bad")));
    strQueue->Enqueue(new CFString(_S("normal")));

    CFString * pStr = new CFString(_S("normal"));
    assert(strQueue->Contains(*pStr));
    pStr->Format(_S("yyyyy"));
    assert( ! strQueue->Contains(*pStr));
    pStr->Format(_S("good"));
    assert(strQueue->Peek()->Equals(*pStr));
    pStr = strQueue->Dequeue();
    assert(pStr->Compare(_S("good")) == 0);
    cppmempool::Release(pStr);
    pStr = NULL;
    assert(strQueue->GetCount() == 2);

    strQueue->Clear();
    assert(strQueue->GetCount() == 0);

    // test out of bound
    try {
       strQueue->Dequeue();
       assert(false);  // should not get this line run
    }
    catch(OutOfBoundsException &) {
    }

    try {
       strQueue->Peek();
       assert(false);  // should not get this line run
    }
    catch(OutOfBoundsException &) {
    }

}

static void TestStack()
{
    cppmempool::MemPoolWrap localPool;

    // stack of integers
    StackInt * intStack = new StackInt(false);
    assert(intStack->GetCount() == 0);
    intStack->Push(3);
    intStack->Push(1);
    intStack->Push(43);
    assert(intStack->GetCount() == 3);
    assert(intStack->Peek() == 43);
    assert(intStack->Pop() == 43);
    assert(intStack->Pop() == 1);
    assert(intStack->GetCount() == 1);
    assert(intStack->Pop() == 3);

    intStack->Push(12);
    intStack->Push(2);
    intStack->Push(412);
    assert(intStack->Contains(2));
    assert(intStack->Contains(412));
    assert(!intStack->Contains(111));
    intStack->Clear();
    assert(intStack->GetCount() == 0);

    try {
       intStack->Pop();
       assert(false);  // should not get this line run
    }
    catch(OutOfBoundsException &) {
    }

    try {
       intStack->Peek();
       assert(false);  // should not get this line run
    }
    catch(OutOfBoundsException &) {
    }

    // stack of BaseObject Objects
    StackCppObjT<CFString> * strStack = new StackCppObjT<CFString>(true);
    strStack->Push(new CFString("hello"));
    strStack->Push(new CFString(" --- "));
    strStack->Push(new CFString("world"));
    assert(strStack->GetCount() == 3);
    assert(strStack->Peek()->Compare(_S("world")) == 0);
    CFString *str = strStack->Pop();
    cppmempool::Release(str);
    str = strStack->Pop();
    cppmempool::Release(str);
    str = strStack->Pop();
    assert(str->Compare(_S("hello")) == 0);
    cppmempool::Release(str);
    assert(strStack->GetCount() == 0);
    
    strStack->Push(new CFString("aaaa"));
    strStack->Push(new CFString("jjjj"));
    assert(strStack->Contains(CFString("aaaa")));
    assert(!strStack->Contains(CFString("bbbb")));
    strStack->Clear();
    assert(strStack->GetCount() == 0);

    try {
       strStack->Pop();
       assert(false);  // should not get this line run
    }
    catch(OutOfBoundsException &) {
    }

    try {
       strStack->Peek();
       assert(false);  // should not get this line run
    }
    catch(OutOfBoundsException &) {
    }

}

static void TestBinBuf(void)
{
    cppmempool::MemPoolWrap localPool;

    BinBuf * pBinBuf = new BinBuf();
    pBinBuf->CopyData((const u8_t*)"hello world", 11, true);
    assert(pBinBuf->GetValidLength() == 11);
    pBinBuf->AppendInt(34);
    assert(pBinBuf->GetValidLength() == 13);
    pBinBuf->AppendUInt(999);
    assert(pBinBuf->GetValidLength() == 16);
    pBinBuf->AppendHex(0x456);
    assert(pBinBuf->GetValidLength() == 19);
    pBinBuf->MoveData2Front(11);
    assert(pBinBuf->GetValidLength() == 8);

}

static void TestLinkedHashtable()
{
   cppmempool::MemPoolWrap localPool;

   LinkedHashtableT<CFString, CFString> *table = new LinkedHashtableT<CFString, CFString>(31);
   assert(table->GetCount() == 0);
   table->Set(new CFString("key1"), new CFString("val1"));
   table->Set(new CFString("key2"), new CFString("val2"));
   table->Set(new CFString("key3"), new CFString("val3"));
   assert(table->GetCount() == 3);

   assert(table->Get(CFString("key1"))->Compare(_S("val1")) == 0);
   assert(table->Get(CFString("key3"))->Compare(_S("val3")) == 0);

   const CFString *pKey = NULL;
   CFString *pVal = NULL;
   table->Get(0, pKey, pVal);
   assert(pKey && pKey->Compare(_S("key1")) == 0);  assert(pVal && pVal->Compare(_S("val1")) == 0);
   table->Get(1, pKey, pVal);
   assert(pKey && pKey->Compare(_S("key2")) == 0);  assert(pVal && pVal->Compare(_S("val2")) == 0);
   table->Get(2, pKey, pVal);
   assert(pKey && pKey->Compare(_S("key3")) == 0);  assert(pVal && pVal->Compare(_S("val3")) == 0);
   table->GetHead(pKey, pVal);
   assert(pKey && pKey->Compare(_S("key1")) == 0);  assert(pVal && pVal->Compare(_S("val1")) == 0);
   table->GetTail(pKey, pVal);
   assert(pKey && pKey->Compare(_S("key3")) == 0);  assert(pVal && pVal->Compare(_S("val3")) == 0);
   
   table->Set(new CFString("key 2a"), new CFString("val 2a"));
   assert(table->GetCount() == 4);
   table->Set(new CFString("key 100"), new CFString("val 100"));  // add one
   assert(table->GetCount() == 5);
   table->Set(new CFString("key2"), new CFString("val hahaha"));  // replace
   assert(table->GetCount() == 5);

   assert(table->ContainsKey(CFString("key 100")));
   assert(!table->ContainsKey(CFString("key @@@@")));
   assert(table->ContainsValue(CFString("val hahaha")));
   assert(!table->ContainsValue(CFString("val ######")));

   table->Remove(CFString("key 100"));
   assert(table->GetCount() == 4);
   table->RemoveAt(1);
   assert(table->GetCount() == 3);
   table->Get(0, pKey, pVal);
   assert(pKey && pKey->Compare(_S("key1")) == 0);  assert(pVal && pVal->Compare(_S("val1")) == 0);
   table->Get(1, pKey, pVal);
   assert(pKey && pKey->Compare(_S("key3")) == 0);  assert(pVal && pVal->Compare(_S("val3")) == 0);
   table->Get(2, pKey, pVal);
   assert(pKey && pKey->Compare(_S("key 2a")) == 0);  assert(pVal && pVal->Compare(_S("val 2a")) == 0);
   
   table->Clear();
   assert(table->GetCount() == 0);

   // test out of bounds
   try {
      table->Get(-1, pKey, pVal);
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   try {
      table->Get(static_cast<int>(table->GetCount()), pKey, pVal);
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   try {
      table->RemoveAt(-1);
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }

   try {
      table->RemoveAt(static_cast<int>(table->GetCount()));
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }
   
} 

static int CmpIntFunc(int a, int b)
{
   return a - b;
}

static int SortCmpIntFunc(ptrany_t a, ptrany_t b)
{
   return *reinterpret_cast<int*>(a) - *reinterpret_cast<int*>(b);
}

static void InitIntList(ListInt *pList)
{
   pList->AddTail(37); pList->AddTail(2); 
   pList->AddTail(4); pList->AddTail(3111); 
   pList->AddTail(9); pList->AddTail(221); 
   pList->AddTail(78); pList->AddTail(114);
   pList->AddTail(35); pList->AddTail(456);
}

static void TestSortingList()
{
   cppmempool::MemPoolWrap localPool;

   // sort whole list
   ListInt *pList = new ListInt();   
   InitIntList(pList);
   ListInt::CmpFuncS cmpFunc(&CmpIntFunc);
   pList->Sort(cmpFunc);
   
   assert(pList->Get(0) == 2); assert(pList->Get(1) == 4);
   assert(pList->Get(2) == 9); assert(pList->Get(3) == 35);
   assert(pList->Get(4) == 37); assert(pList->Get(5) == 78);
   assert(pList->Get(6) == 114); assert(pList->Get(7) == 221);
   assert(pList->Get(8) == 456); assert(pList->Get(9) == 3111);
   
   // sort partial list 1 (front 5)
   pList = new ListInt();   
   InitIntList(pList);
   pList->Sort(0, 5, cmpFunc);

   assert(pList->Get(0) == 2); assert(pList->Get(1) == 4);
   assert(pList->Get(2) == 9); assert(pList->Get(3) == 37);
   assert(pList->Get(4) == 3111); assert(pList->Get(5) == 221);
   assert(pList->Get(6) == 78); assert(pList->Get(7) == 114);
   assert(pList->Get(8) == 35); assert(pList->Get(9) == 456);

   // sort partial list 2 (tail 5)
   pList = new ListInt();   
   InitIntList(pList);
   util::FuncPtr2T<int, ptrany_t, ptrany_t> sortCmpFunc(&SortCmpIntFunc);
   HeapSort(*pList, 5, 5, sortCmpFunc);

   assert(pList->Get(0) == 37); assert(pList->Get(1) == 2);
   assert(pList->Get(2) == 4); assert(pList->Get(3) == 3111);
   assert(pList->Get(4) == 9); assert(pList->Get(5) == 35);
   assert(pList->Get(6) == 78); assert(pList->Get(7) == 114);
   assert(pList->Get(8) == 221); assert(pList->Get(9) == 456);

   // sort partial list 3 (middle 6)
   pList = new ListInt();   
   InitIntList(pList);
   HeapSort(*pList, 2, 6, sortCmpFunc);

   assert(pList->Get(0) == 37); assert(pList->Get(1) == 2);
   assert(pList->Get(2) == 4); assert(pList->Get(3) == 9);
   assert(pList->Get(4) == 78); assert(pList->Get(5) == 114);
   assert(pList->Get(6) == 221); assert(pList->Get(7) == 3111);
   assert(pList->Get(8) == 35); assert(pList->Get(9) == 456);

   // sort partial list 4 (middle 2)
   pList = new ListInt();   
   InitIntList(pList);
   HeapSort(*pList, 3, 2, sortCmpFunc);

   assert(pList->Get(0) == 37); assert(pList->Get(1) == 2);
   assert(pList->Get(2) == 4); assert(pList->Get(3) == 9);
   assert(pList->Get(4) == 3111); assert(pList->Get(5) == 221);
   assert(pList->Get(6) == 78); assert(pList->Get(7) == 114);
   assert(pList->Get(8) == 35); assert(pList->Get(9) == 456);

   // sort partial list 5 (tail 7)
   pList = new ListInt();   
   InitIntList(pList);
   HeapSort(*pList, 3, 7, sortCmpFunc);

   assert(pList->Get(0) == 37); assert(pList->Get(1) == 2);
   assert(pList->Get(2) == 4); assert(pList->Get(3) == 9);
   assert(pList->Get(4) == 35); assert(pList->Get(5) == 78);
   assert(pList->Get(6) == 114); assert(pList->Get(7) == 221);
   assert(pList->Get(8) == 456); assert(pList->Get(9) == 3111);

   // test sorting out of range
   try {
      pList->Sort(4, 10, cmpFunc);
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }
   
}

static int CmpStringFunc(CFString * a, CFString * b)
{
   return a->Compare(*b);
}


static int SortCmpStringFunc(ptrany_t ele1, ptrany_t ele2)
{
   CFString * a = reinterpret_cast<CFString*>(ele1);
   CFString * b = reinterpret_cast<CFString*>(ele2);
   return a->Compare(*b);
}

static void InitStringList(ListCppObjT<CFString> *pList)
{
   pList->AddTail(new CFString("The")); pList->AddTail(new CFString("delegation")); 
   pList->AddTail(new CFString("will")); pList->AddTail(new CFString("ask"));
   pList->AddTail(new CFString("Niger")); pList->AddTail(new CFString("to"));
   pList->AddTail(new CFString("hand")); pList->AddTail(new CFString("over"));
   pList->AddTail(new CFString("Saadi")); pList->AddTail(new CFString("Gadhafi"));
}

static void TestSortingList_2()
{
   cppmempool::MemPoolWrap localPool;

   // sort whole list
   ListCppObjT<CFString> *pList = new ListCppObjT<CFString>();
   InitStringList(pList);
   ListCppObjT<CFString>::CmpFuncS cmpFunc(&CmpStringFunc);
   //ListCppObjT<CFString>::CmpFunc cmpFunc(&CmpStringFunc);
   pList->Sort(cmpFunc);
   assert(*pList->Get(0) == _S("Gadhafi")); assert(*pList->Get(1) == _S("Niger")); assert(*pList->Get(2) == _S("Saadi")); assert(*pList->Get(3) == _S("The"));
   assert(*pList->Get(4) == _S("ask")); assert(*pList->Get(5) == _S("delegation")); assert(*pList->Get(6) == _S("hand")); assert(*pList->Get(7) == _S("over"));
   assert(*pList->Get(8) == _S("to")); assert(*pList->Get(9) == _S("will"));
   
   // sort partial list 1 (front 5)
   pList = new ListCppObjT<CFString>();
   InitStringList(pList);
   pList->Sort(0, 5, cmpFunc);
   assert(*pList->Get(0) == _S("Niger")); assert(*pList->Get(1) == _S("The")); assert(*pList->Get(2) == _S("ask")); assert(*pList->Get(3) == _S("delegation"));
   assert(*pList->Get(4) == _S("will")); assert(*pList->Get(5) == _S("to")); assert(*pList->Get(6) == _S("hand")); assert(*pList->Get(7) == _S("over"));
   assert(*pList->Get(8) == _S("Saadi")); assert(*pList->Get(9) == _S("Gadhafi"));

   // sort partial list 2 (tail 5)
   pList = new ListCppObjT<CFString>();
   InitStringList(pList);
   util::FuncPtr2T<int, ptrany_t, ptrany_t> sortCmpFunc(&SortCmpStringFunc);
   HeapSort(*pList, 5, 5, sortCmpFunc);
   assert(*pList->Get(0) == _S("The")); assert(*pList->Get(1) == _S("delegation")); assert(*pList->Get(2) == _S("will")); assert(*pList->Get(3) == _S("ask"));
   assert(*pList->Get(4) == _S("Niger")); assert(*pList->Get(5) == _S("Gadhafi")); assert(*pList->Get(6) == _S("Saadi")); assert(*pList->Get(7) == _S("hand"));
   assert(*pList->Get(8) == _S("over")); assert(*pList->Get(9) == _S("to"));

   // sort partial list 3 (middle 6)
   pList = new ListCppObjT<CFString>();
   InitStringList(pList);
   HeapSort(*pList, 2, 6, sortCmpFunc);
   assert(*pList->Get(0) == _S("The")); assert(*pList->Get(1) == _S("delegation")); assert(*pList->Get(2) == _S("Niger")); assert(*pList->Get(3) == _S("ask"));
   assert(*pList->Get(4) == _S("hand")); assert(*pList->Get(5) == _S("over")); assert(*pList->Get(6) == _S("to")); assert(*pList->Get(7) == _S("will"));
   assert(*pList->Get(8) == _S("Saadi")); assert(*pList->Get(9) == _S("Gadhafi"));

   // test sorting out of range
   try {
      pList->Sort(4, 10, cmpFunc);
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }
}

static void InitArrayInt(ArrayInt & pArray)
{
   pArray[0] = 37; pArray[1] = 2; 
   pArray[2] = 4; pArray[3] = 3111; 
   pArray[4] = 9; pArray[5] = 221; 
   pArray[6] = 78; pArray[7] = 114;
   pArray[8] = 35; pArray[9] = 456;
}

static void TestSortingArray()
{
   cppmempool::MemPoolWrap localPool;

   // sort whole array
   ArrayInt * pArray = new ArrayInt(10);
   InitArrayInt(*pArray);
   ArrayInt::CmpFuncS cmpFunc(&CmpIntFunc);
   pArray->Sort(cmpFunc);
   assert((*pArray)[0] == 2); assert((*pArray)[1] == 4);
   assert((*pArray)[2] == 9); assert((*pArray)[3] == 35);
   assert((*pArray)[4] == 37); assert((*pArray)[5] == 78);
   assert((*pArray)[6] == 114); assert((*pArray)[7] == 221);
   assert((*pArray)[8] == 456); assert((*pArray)[9] == 3111);
   
   // sort partial array 1 (front 5)
   pArray = new ArrayInt(10);
   InitArrayInt(*pArray);
   pArray->Sort(0, 5, cmpFunc);

   assert((*pArray)[0] == 2); assert((*pArray)[1] == 4);
   assert((*pArray)[2] == 9); assert((*pArray)[3] == 37);
   assert((*pArray)[4] == 3111); assert((*pArray)[5] == 221);
   assert((*pArray)[6] == 78); assert((*pArray)[7] == 114);
   assert((*pArray)[8] == 35); assert((*pArray)[9] == 456);

   // sort partial array 2 (tail 5)
   pArray = new ArrayInt(10);
   InitArrayInt(*pArray);
   util::FuncPtr2T<int, ptrany_t, ptrany_t> sortCmpFunc(&SortCmpIntFunc);
   HeapSort(*pArray, 5, 5, sortCmpFunc);

   assert((*pArray)[0] == 37); assert((*pArray)[1] == 2);
   assert((*pArray)[2] == 4); assert((*pArray)[3] == 3111);
   assert((*pArray)[4] == 9); assert((*pArray)[5] == 35);
   assert((*pArray)[6] == 78); assert((*pArray)[7] == 114);
   assert((*pArray)[8] == 221); assert((*pArray)[9] == 456);

   // sort partial array 3 (middle 6)
   pArray = new ArrayInt(10);
   InitArrayInt(*pArray);
   HeapSort(*pArray, 2, 6, sortCmpFunc);

   assert((*pArray)[0] == 37); assert((*pArray)[1] == 2);
   assert((*pArray)[2] == 4); assert((*pArray)[3] == 9);
   assert((*pArray)[4] == 78); assert((*pArray)[5] == 114);
   assert((*pArray)[6] == 221); assert((*pArray)[7] == 3111);
   assert((*pArray)[8] == 35); assert((*pArray)[9] == 456);

   // sort partial array 4 (middle 2)
   pArray = new ArrayInt(10);
   InitArrayInt(*pArray);
   HeapSort(*pArray, 3, 2, sortCmpFunc);

   assert((*pArray)[0] == 37); assert((*pArray)[1] == 2);
   assert((*pArray)[2] == 4); assert((*pArray)[3] == 9);
   assert((*pArray)[4] == 3111); assert((*pArray)[5] == 221);
   assert((*pArray)[6] == 78); assert((*pArray)[7] == 114);
   assert((*pArray)[8] == 35); assert((*pArray)[9] == 456);

   // sort partial array 5 (tail 7)
   pArray = new ArrayInt(10);
   InitArrayInt(*pArray);
   HeapSort(*pArray, 3, 7, sortCmpFunc);

   assert((*pArray)[0] == 37); assert((*pArray)[1] == 2);
   assert((*pArray)[2] == 4); assert((*pArray)[3] == 9);
   assert((*pArray)[4] == 35); assert((*pArray)[5] == 78);
   assert((*pArray)[6] == 114); assert((*pArray)[7] == 221);
   assert((*pArray)[8] == 456); assert((*pArray)[9] == 3111);

   // test sorting out of range
   try {
      pArray->Sort(4, 10, cmpFunc);
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }
}

static void InitStringArray(ArrayCppObjT<CFString> *pArray)
{
   pArray->Set(0, new CFString("The")); pArray->Set(1, new CFString("delegation")); 
   pArray->Set(2, new CFString("will")); pArray->Set(3, new CFString("ask"));
   pArray->Set(4, new CFString("Niger")); pArray->Set(5, new CFString("to"));
   pArray->Set(6, new CFString("hand")); pArray->Set(7, new CFString("over"));
   pArray->Set(8, new CFString("Saadi")); pArray->Set(9, new CFString("Gadhafi"));
}

static void TestSortingArray_2()
{
   cppmempool::MemPoolWrap localPool;

   ArrayCppObjT<CFString> *pArray = new ArrayCppObjT<CFString>(10);
   InitStringArray(pArray);
   ArrayCppObjT<CFString>::CmpFuncS cmpFunc(&CmpStringFunc);
   pArray->Sort(cmpFunc);
   assert(*pArray->Get(0) == _S("Gadhafi")); assert(*pArray->Get(1) == _S("Niger")); assert(*pArray->Get(2) == _S("Saadi")); assert(*pArray->Get(3) == _S("The"));
   assert(*pArray->Get(4) == _S("ask")); assert(*pArray->Get(5) == _S("delegation")); assert(*pArray->Get(6) == _S("hand")); assert(*pArray->Get(7) == _S("over"));
   assert(*pArray->Get(8) == _S("to")); assert(*pArray->Get(9) == _S("will"));
   
   // sort partial array 1 (front 5)
   pArray = new ArrayCppObjT<CFString>(10);
   InitStringArray(pArray);
   pArray->Sort( 0, 5, cmpFunc);
   assert(*pArray->Get(0) == _S("Niger")); assert(*pArray->Get(1) == _S("The")); assert(*pArray->Get(2) == _S("ask")); assert(*pArray->Get(3) == _S("delegation"));
   assert(*pArray->Get(4) == _S("will")); assert(*pArray->Get(5) == _S("to")); assert(*pArray->Get(6) == _S("hand")); assert(*pArray->Get(7) == _S("over"));
   assert(*pArray->Get(8) == _S("Saadi")); assert(*pArray->Get(9) == _S("Gadhafi"));

   // sort partial array 2 (tail 5)
   pArray = new ArrayCppObjT<CFString>(10);
   InitStringArray(pArray);
   util::FuncPtr2T<int, ptrany_t, ptrany_t> sortCmpFunc(&SortCmpStringFunc);
   HeapSort(*pArray, 5, 5, sortCmpFunc);
   assert(*pArray->Get(0) == _S("The")); assert(*pArray->Get(1) == _S("delegation")); assert(*pArray->Get(2) == _S("will")); assert(*pArray->Get(3) == _S("ask"));
   assert(*pArray->Get(4) == _S("Niger")); assert(*pArray->Get(5) == _S("Gadhafi")); assert(*pArray->Get(6) == _S("Saadi")); assert(*pArray->Get(7) == _S("hand"));
   assert(*pArray->Get(8) == _S("over")); assert(*pArray->Get(9) == _S("to"));

   // sort partial array 3 (middle 6)
   pArray = new ArrayCppObjT<CFString>(10);
   InitStringArray(pArray);
   HeapSort(*pArray, 2, 6, sortCmpFunc);
   assert(*pArray->Get(0) == _S("The")); assert(*pArray->Get(1) == _S("delegation")); assert(*pArray->Get(2) == _S("Niger")); assert(*pArray->Get(3) == _S("ask"));
   assert(*pArray->Get(4) == _S("hand")); assert(*pArray->Get(5) == _S("over")); assert(*pArray->Get(6) == _S("to")); assert(*pArray->Get(7) == _S("will"));
   assert(*pArray->Get(8) == _S("Saadi")); assert(*pArray->Get(9) == _S("Gadhafi"));

   // test sorting out of range
   try {
      pArray->Sort(4, 10, cmpFunc);
      assert(false);  // should not get this line run
   }
   catch(OutOfBoundsException &) {
   }
}

static void TestCircularBuffer()
{
   cppmempool::MemPoolWrap localPool;
   const int CIRCULARBUFSIZE = 12;
   const int BUFSIZE = CIRCULARBUFSIZE + 1;
   char letters[] = "hello";
   char letters2[] = "1234567890abcd";
   char buffer[BUFSIZE] = {0};
   sz_t retLen = 0;

   CircularBuffer *pBuf = new CircularBuffer(CIRCULARBUFSIZE);
   assert(pBuf->GetValidLength() == 0);
   assert(pBuf->GetLength() == CIRCULARBUFSIZE);
   
   pBuf->CopyData(reinterpret_cast<const u8_t*>(letters), strlen(letters));
   assert(pBuf->GetValidLength() == 5);
   retLen = pBuf->GetData(reinterpret_cast<u8_t*>(buffer), CIRCULARBUFSIZE, 0); 
   assert(retLen == 5);
   buffer[retLen] = '\0';
   assert(strcmp(buffer, "hello") == 0);
   
   pBuf->AppendData(reinterpret_cast<const u8_t*>(letters), strlen(letters));
   assert(pBuf->GetValidLength() == 10);
   retLen = pBuf->GetData(reinterpret_cast<u8_t*>(buffer), CIRCULARBUFSIZE, 0); 
   assert(retLen == 10);
   buffer[retLen] = '\0';
   assert(strcmp(buffer, "hellohello") == 0);

   pBuf->AppendData(reinterpret_cast<const u8_t*>(letters), strlen(letters));
   assert(pBuf->GetValidLength() == CIRCULARBUFSIZE);
   retLen = pBuf->GetData(reinterpret_cast<u8_t*>(buffer), CIRCULARBUFSIZE, 0); 
   assert(retLen == CIRCULARBUFSIZE);
   buffer[retLen] = '\0';
   assert(strcmp(buffer, "lohellohello") == 0);

   pBuf->AppendData(reinterpret_cast<const u8_t*>(letters), strlen(letters));
   assert(pBuf->GetValidLength() == CIRCULARBUFSIZE);
   retLen = pBuf->GetData(reinterpret_cast<u8_t*>(buffer), CIRCULARBUFSIZE, 0); 
   assert(retLen == CIRCULARBUFSIZE);
   buffer[retLen] = '\0';
   assert(strcmp(buffer, "lohellohello") == 0);

   retLen = pBuf->GetData(reinterpret_cast<u8_t*>(buffer), CIRCULARBUFSIZE, 5); 
   assert(retLen == 7);
   buffer[retLen] = '\0';
   assert(strcmp(buffer, "lohello") == 0);

   pBuf->AppendData(reinterpret_cast<const u8_t*>(letters), 1);
   assert(pBuf->GetValidLength() == CIRCULARBUFSIZE);
   retLen = pBuf->GetData(reinterpret_cast<u8_t*>(buffer), CIRCULARBUFSIZE, 0); 
   assert(retLen == CIRCULARBUFSIZE);
   buffer[retLen] = '\0';
   assert(strcmp(buffer, "ohellohelloh") == 0);

   pBuf->AppendData(reinterpret_cast<const u8_t*>(letters), 1);
   assert(pBuf->GetValidLength() == CIRCULARBUFSIZE);
   retLen = pBuf->GetData(reinterpret_cast<u8_t*>(buffer), CIRCULARBUFSIZE, 0); 
   assert(retLen == CIRCULARBUFSIZE);
   buffer[retLen] = '\0';
   assert(strcmp(buffer, "hellohellohh") == 0);

   pBuf->AppendData(reinterpret_cast<const u8_t*>(letters2), CIRCULARBUFSIZE);
   assert(pBuf->GetValidLength() == CIRCULARBUFSIZE);
   retLen = pBuf->GetData(reinterpret_cast<u8_t*>(buffer), CIRCULARBUFSIZE, 0); 
   assert(retLen == CIRCULARBUFSIZE);
   buffer[retLen] = '\0';
   assert(strcmp(buffer, "1234567890ab") == 0);

   pBuf->AppendData(reinterpret_cast<const u8_t*>(letters2), CIRCULARBUFSIZE + 2);
   assert(pBuf->GetValidLength() == CIRCULARBUFSIZE);
   retLen = pBuf->GetData(reinterpret_cast<u8_t*>(buffer), CIRCULARBUFSIZE, 8); 
   assert(retLen == 4);
   buffer[retLen] = '\0';
   assert(strcmp(buffer, "abcd") == 0);

   pBuf->CopyData(reinterpret_cast<const u8_t*>(letters), strlen(letters));
   assert(pBuf->GetValidLength() == 5);
   retLen = pBuf->GetData(reinterpret_cast<u8_t*>(buffer), CIRCULARBUFSIZE, 0); 
   assert(retLen == 5);
   buffer[retLen] = '\0';
   assert(strcmp(buffer, "hello") == 0);
}

static int mctreeNodeCount = 0;
static void MCTreewalkcb(MCTreeNode & node)
{
/*
   CFString s;
   for (u32_t i = 0; i < node.GetDepth(); ++i)
      s.AppendFormat(_S("  "));

   debug::Print(debug::DL_DEBUG, _S("%s%s\n"), static_cast<pcwstr_t>(s), node.GetKey()->ToString());
*/
   ++mctreeNodeCount;
}

static void TestMultiChildTree()
{
   debug::Print(_S("Testing Multi child tree...\n"));

   cppmempool::MemPoolWrap memPool;

   MultiChildTree *pTree = new MultiChildTree(true);
   MCTreeNode *pRootNode = new MCTreeNode(new CFString(_S("root")));
   MCTreeNode *pChildNode = NULL;

   assert(pTree->IsTreeEmpty());
   assert(pTree->GetTotalNodeCount() == 0);

   pTree->SetRootNode(pRootNode);
   
   assert(!pTree->IsTreeEmpty());
   assert(pTree->GetTotalNodeCount() == 1);
   assert(pRootNode->GetAttachedTree() == pTree);
   assert(pRootNode->GetDirectChildCount() == 0);
   assert(pRootNode->GetNextSibling() == NULL);
   assert(pRootNode->GetPrevSibling() == NULL);
   assert(pRootNode->IsRootNode());
   assert(pRootNode->GetDepth() == 0);

   pChildNode = new MCTreeNode(new CFString(_S("child-1")));
   pRootNode->AddChild(pChildNode);
   assert(pRootNode->GetDirectChildCount() == 1);
   assert(pChildNode->GetParent() == pRootNode);
   assert(pChildNode->GetNextSibling() == NULL);
   assert(pChildNode->GetPrevSibling() == NULL);
   assert(!pChildNode->IsRootNode());
   assert(pChildNode->GetDepth() == 1);
   assert(pTree->GetTotalNodeCount() == 2);

   MCTreeNode *pGrandChildNode = new MCTreeNode(new CFString(_S("grand child-1")));
   try { pTree->SetRootNode(pGrandChildNode); assert(false); }
   catch (RuntimeException &e) { debug::Print(debug::DL_DEBUG, _S("%s\n"), e.GetMsg()); }
   try { pGrandChildNode->GetNextSibling(); assert(false); }
   catch (RuntimeException &e) { debug::Print(debug::DL_DEBUG, _S("%s\n"), e.GetMsg()); }
   try { pGrandChildNode->IsRootNode(); assert(false); }
   catch (RuntimeException &e) { debug::Print(debug::DL_DEBUG, _S("%s\n"), e.GetMsg()); }

   pChildNode->AddChild(pGrandChildNode);
   assert(pChildNode->GetDirectChildCount() == 1);
   assert(pGrandChildNode->GetParent() == pChildNode);
   assert(pRootNode->GetAllChildCount() == 2);
   assert(pTree->GetTotalNodeCount() == 3);
   assert(pGrandChildNode->GetDepth() == 2);

   pChildNode = new MCTreeNode(new CFString(_S("child-2")));
   pRootNode->AddChild(pChildNode);
   assert(pRootNode->GetDirectChildCount() == 2);
   assert(pChildNode->GetParent() == pRootNode);
   assert(pChildNode->GetNextSibling() == NULL);
   MCTreeNode *pTempNode = pChildNode->GetPrevSibling();
   assert(pTempNode != NULL);
   assert(pTempNode->GetKey()->Equals(CFString(_S("child-1"))));
   assert(!pChildNode->IsRootNode());
   assert(pChildNode->GetDepth() == 1);
   assert(pTree->GetTotalNodeCount() == 4);

   assert(!pRootNode->AddChild(new MCTreeNode(new CFString(_S("child-1"))))); // same name
   assert(!pRootNode->AddChild(new MCTreeNode(new CFString(_S("child-2"))))); // same name

   pGrandChildNode = new MCTreeNode(new CFString(_S("grand child-2")));
   pChildNode->AddChild(pGrandChildNode);
   assert(pChildNode->GetDirectChildCount() == 1);
   assert(pGrandChildNode->GetParent() == pChildNode);
   assert(pTree->GetTotalNodeCount() == 5);
   assert(pGrandChildNode->GetDepth() == 2);

   pChildNode = new MCTreeNode(new CFString(_S("child-3")));
   pRootNode->AddChild(pChildNode);
   assert(pRootNode->GetDirectChildCount() == 3);
   assert(pChildNode->GetParent() == pRootNode);
   assert(pChildNode->GetNextSibling() == NULL);
   assert(pChildNode->GetPrevSibling() != NULL);
   assert(!pChildNode->IsRootNode());
   assert(pChildNode->GetDepth() == 1);
   assert(pTree->GetTotalNodeCount() == 6);
   assert(pRootNode->GetAllChildCount() == 5);

   pTempNode = pRootNode->GetChild(1);
   assert(pTempNode != NULL);
   assert(pTempNode->GetNextSibling() == pChildNode);

   // traverse tree
   debug::Print(_S("----------------------------\n"));
   mctreeNodeCount = 0;
   pTree->TraverseTree(MCTreeWalkCallback(&MCTreewalkcb));
   assert(mctreeNodeCount == 6);

   // child of grand child
   pGrandChildNode->AddChild(new MCTreeNode(new CFString(_S("gg child")))); 
   // move node and traverse again
   assert(!pRootNode->Move(pGrandChildNode));
   assert(!pGrandChildNode->Move(pGrandChildNode));
   assert(!pRootNode->GetChild(1)->Move(pGrandChildNode));
   assert(pGrandChildNode->Move(pRootNode));
   debug::Print(_S("----------------------------\n"));
   mctreeNodeCount = 0;
   pTree->TraverseTree(MCTreeWalkCallback(&MCTreewalkcb));
   assert(mctreeNodeCount == 7);

   // move back
   assert(pGrandChildNode->Move(pRootNode->GetChild(1)));
   debug::Print(_S("----------------------------\n"));
   mctreeNodeCount = 0;
   pTree->TraverseTree(MCTreeWalkCallback(&MCTreewalkcb));
   assert(mctreeNodeCount == 7);


   assert(!pRootNode->DeleteChild(3));
   assert(pRootNode->DeleteChild(1));  // will delete grand child as well
   assert(pRootNode->GetDirectChildCount() == 2);
   assert(pTree->GetTotalNodeCount() == 4);
   assert(pRootNode->GetChild(0)->GetNextSibling() == pChildNode);
   assert(pRootNode->DeleteChild(CFString(_S("child-3"))));
   assert(pRootNode->GetDirectChildCount() == 1);
   assert(pTree->GetTotalNodeCount() == 3);
   pTree->FreeTree();
   assert(pTree->GetTotalNodeCount() == 0);
}

static void TestMultiChildTree_2()
{
   debug::Print(_S("Testing Multi child tree 2...\n"));

   cppmempool::MemPoolWrap memPool;

   MultiChildTree *pTree = new MultiChildTree(false);  // allow duplicated keys
   MCTreeNode *pRootNode = new MCTreeNode(new CFString(_S("root")));

   pTree->SetRootNode(pRootNode);
   assert(pRootNode->AddChild(new MCTreeNode(new CFString(_S("child-1")))));
   assert(pRootNode->AddChild(new MCTreeNode(new CFString(_S("child-1")))));
   assert(pRootNode->AddChild(new MCTreeNode(new CFString(_S("child-1")))));
   
   MCTreeNode *pChildNode = pRootNode->GetChild(1);
   assert(pChildNode->AddChild(new MCTreeNode(new CFString(_S("grand child")))));
   assert(pTree->GetTotalNodeCount() == 5);

   // traverse tree
   debug::Print(_S("----------------------------\n"));
   mctreeNodeCount = 0;
   pTree->TraverseTree(MCTreeWalkCallback(&MCTreewalkcb));
   assert(mctreeNodeCount == 5);

   assert(pChildNode->GetChild(0)->Move(pRootNode));
   assert(pChildNode->GetNextSibling()->GetNextSibling()->GetKey()->Equals(CFString(_S("grand child"))));
   assert(pChildNode->GetNextSibling() == pRootNode->GetChild(3)->GetPrevSibling());

   // traverse tree
   debug::Print(_S("----------------------------\n"));
   mctreeNodeCount = 0;
   pTree->TraverseTree(MCTreeWalkCallback(&MCTreewalkcb));
   assert(mctreeNodeCount == 5);
   // move back
   assert(pRootNode->GetChild(3)->Move(pChildNode));

   // traverse tree
   debug::Print(_S("----------------------------\n"));
   mctreeNodeCount = 0;
   pTree->TraverseTree(MCTreeWalkCallback(&MCTreewalkcb));
   assert(mctreeNodeCount == 5);

   pRootNode->DeleteChild(1);
   assert(pTree->GetTotalNodeCount() == 3);
   assert(pRootNode->DeleteChild(CFString(_S("child-1"))));
   assert(pRootNode->DeleteChild(CFString(_S("child-1"))));
   assert(!pRootNode->DeleteChild(CFString(_S("child-1"))));
   pTree->FreeTree();
   assert(pTree->GetTotalNodeCount() == 0);

}

static int nodeCount_3 = 0;
static void MCTreewalkcb_3(MCTreeNode & node)
{
   const CFString * pKey = static_cast<const CFString *>(node.GetKey());
   switch (node.GetDepth()) {
      case 0:
         assert(pKey->Compare(_S("root")) == 0);
         break;
      case 1:
         assert(pKey->Compare(_S("child-1")) == 0);
         break;
      case 2:
         assert(pKey->Compare(_S("child-2")) == 0);
         break;
      case 3:
         assert(pKey->Compare(_S("child-3")) == 0);
         break;
   }
/*
   CFString s;
   for (u32_t i = 0; i < node.GetDepth(); ++i)
      s.AppendFormat(_S("  "));

   debug::Print(debug::DL_DEBUG, _S("%s%s\n"), static_cast<pcwstr_t>(s), pKey->ToString());
*/
   ++nodeCount_3;
}

static int nodeCount_4 = 0;
static void MCTreewalkcb_4(MCTreeNode & node)
{
   const CFString * pKey = static_cast<const CFString *>(node.GetKey());
   switch (node.GetDepth()) {
      case 0:
         assert(pKey->Compare(_S("child-1")) == 0);
         break;
      case 1:
         assert(pKey->Compare(_S("child-2")) == 0);
         break;
      case 2:
         assert(pKey->Compare(_S("child-3")) == 0);
         break;
   }

   ++nodeCount_4;
}

static void TestMultiChildTree_3()
{
   debug::Print(_S("Testing Multi child tree 3...\n"));

   cppmempool::MemPoolWrap memPool;

   MultiChildTree *pTree = new MultiChildTree(false);  // allow duplicated keys
   pTree->SetRootNode(new MCTreeNode(new CFString(_S("root"))));
   MCTreeNode * pNode = pTree->GetRootNode();
   for (int i = 0; i < 3; ++i) {
      pNode->AddChild(new MCTreeNode(new CFString(_S("child-1"))));
      MCTreeNode * pSubNode = pNode->GetChild(i);
      for (int j = 0; j < 3; ++j) {
         pSubNode->AddChild(new MCTreeNode(new CFString(_S("child-2"))));
         MCTreeNode * pSubSubNode = pSubNode->GetChild(j);
         for (int k = 0; k < 3; ++k) {
            pSubSubNode->AddChild(new MCTreeNode(new CFString(_S("child-3"))));
         }
      }
   }

   // traverse tree
   nodeCount_3 = 0;
   pTree->TraverseTree(MCTreeWalkCallback(&MCTreewalkcb_3));
   assert(nodeCount_3 == 40);


   // detach a node from tree
   pNode = pTree->GetRootNode()->GetChild(1);
   pNode->DetachFromTree();

   nodeCount_3 = 0;
   pTree->TraverseTree(MCTreeWalkCallback(&MCTreewalkcb_3));
   assert(nodeCount_3 == (40 - 13));


   // create another tree
   MultiChildTree *pTree2 = new MultiChildTree(false);
   pTree2->SetRootNode(new MCTreeNode(new CFString(_S("root"))));
   pTree2->GetRootNode()->AddChild(pNode);

   nodeCount_3 = 0;
   pTree2->TraverseTree(MCTreeWalkCallback(&MCTreewalkcb_3));
   assert(nodeCount_3 == 14);
   
   pNode = pTree2->GetRootNode()->GetChild(0);
   pNode->DetachFromTree();
   assert(pTree2->GetTotalNodeCount() == 1);
   
   // create another tree
   MultiChildTree *pTree3 = new MultiChildTree(false);
   pTree3->SetRootNode(pNode);
   assert(pTree3->GetTotalNodeCount() == 13);
   
   nodeCount_4 = 0;
   pTree3->TraverseTree(MCTreeWalkCallback(&MCTreewalkcb_4));
   assert(nodeCount_4 == 13);
}

static void TestKeyValueList()
{
   cppmempool::MemPoolWrap memPool;

   NameValueList * pList = new NameValueList();

   pList->AddTail(new CFString("name1"), new CFString("value1"));
   pList->AddTail(new CFString("name1"), new CFString("value1"));
   pList->AddTail(new CFString("name2"), new CFString("value2"));
   pList->AddTail(new CFString("name3"), new CFString("value3"));

   assert(pList->GetCount() == 4);
   assert(pList->GetKey(1)->Compare(_S("name1")) == 0);
   assert(pList->GetKey(3)->Compare(_S("name3")) == 0);

   assert(pList->GetVal(2)->Compare(_S("value2")) == 0);
   assert(pList->GetVal(0)->Compare(_S("value1")) == 0);
   
   pList->RemoveAt(3);
   assert(pList->GetCount() == 3);
   pList->RemoveAt(2);
   assert(pList->GetCount() == 2);

   assert(pList->RemoveByKey(CFString("name1")) == 2);
   assert(pList->GetCount() == 0);

   assert(pList->RemoveByKey(CFString("name1")) == 0);
   assert(pList->GetCount() == 0);
   pList->Clear();
   assert(pList->GetCount() == 0);
   
   pList->AddTail(new CFString("name2"), new CFString("value2"));
   pList->AddTail(new CFString("name2"), new CFString("value3"));
   pList->AddTail(new CFString("name2"), new CFString("value3"));

   assert(pList->RemoveByValue(CFString("value3")) == 2);
   assert(pList->GetCount() == 1);

   pList->AddTail(new CFString("xxxx2"), new CFString("yyyyy"));
   pList->AddTail(new CFString("xxxx2"), new CFString("yyyyy"));
   pList->AddTail(new CFString("xxxx2"), new CFString("yyyyy"));

   assert(pList->GetCount() == 4);

   pList->Set(3, new CFString("x"), new CFString("y"));
   pList->Insert(1, new CFString("1"), new CFString("2"));

   assert(pList->GetCount() == 5);
   assert(pList->GetKey(1)->Compare(_S("1")) == 0);
   assert(pList->GetVal(1)->Compare(_S("2")) == 0);
   assert(pList->GetKey(4)->Compare(_S("x")) == 0);
   assert(pList->GetVal(4)->Compare(_S("y")) == 0);
   NameValueList * pNewList = pList->Copy();

   pList->Clear();
   assert(pList->GetCount() == 0);

   pNewList->AddHead(new CFString("xxxx2"), new CFString("yyyyy"));
   assert(pNewList->GetCount() == 6);
   assert(pNewList->GetKey(2)->Compare(_S("1")) == 0);
   assert(pNewList->GetVal(2)->Compare(_S("2")) == 0);
   assert(pNewList->GetKey(5)->Compare(_S("x")) == 0);
   assert(pNewList->GetVal(5)->Compare(_S("y")) == 0);

}

static int CmpKeyFunc(ptrany_t ele1, ptrany_t ele2)
{
   CFString * a = reinterpret_cast<CFString*>(ele1);
   CFString * b = reinterpret_cast<CFString*>(ele2);
   return a->Compare(*b);
}

static void TestSortingNameValueList()
{
   cppmempool::MemPoolWrap memPool;

   NameValueList * pList = new NameValueList();

   pList->AddTail(new CFString("name1"), new CFString("value1"));
   pList->AddTail(new CFString("b1"), new CFString("value2"));
   pList->AddTail(new CFString("name1"), new CFString("value1"));
   pList->AddTail(new CFString("name3"), new CFString("value4"));
   pList->AddTail(new CFString("name2"), new CFString("value5"));
   pList->AddTail(new CFString("a1"), new CFString("value6"));
   pList->AddTail(new CFString("name4"), new CFString("value7"));

   util::FuncPtr2T<int, ptrany_t, ptrany_t> cmpFunc(&CmpKeyFunc);
   pList->SortByKey(cmpFunc);
   assert(pList->GetKey(0)->Compare(_S("a1")) == 0);  assert(pList->GetVal(0)->Compare(_S("value6")) == 0);
   assert(pList->GetKey(1)->Compare(_S("b1")) == 0);  assert(pList->GetVal(1)->Compare(_S("value2")) == 0);
   assert(pList->GetKey(2)->Compare(_S("name1")) == 0);  assert(pList->GetVal(2)->Compare(_S("value1")) == 0);
   assert(pList->GetKey(3)->Compare(_S("name1")) == 0);  assert(pList->GetVal(3)->Compare(_S("value1")) == 0);
   assert(pList->GetKey(4)->Compare(_S("name2")) == 0);  assert(pList->GetVal(4)->Compare(_S("value5")) == 0);
   assert(pList->GetKey(5)->Compare(_S("name3")) == 0);  assert(pList->GetVal(5)->Compare(_S("value4")) == 0);
   assert(pList->GetKey(6)->Compare(_S("name4")) == 0);  assert(pList->GetVal(6)->Compare(_S("value7")) == 0);

}

void TestCollections()
{
   debug::Print(_S("Testing Collections...\n"));

   TestArrayTemplate();
   TestCopyArray();
   TestListTemplate();
   TestListPtrTemplate();
   TestHashtable();
   TestBinTree();
   TestAvlTree();
   TestAvlTree_2();
   TestMultiChildTree();
   TestMultiChildTree_2();
   TestMultiChildTree_3();
   TestQueue();
   TestStack();
   TestBinBuf();
   TestLinkedHashtable();

   debug::Print(_S("Testing sorting collections...\n"));
   TestSortingList();
   TestSortingList_2();
   TestSortingArray();
   TestSortingArray_2();
   TestCircularBuffer();
   TestKeyValueList();
   TestSortingNameValueList();

}


